package org.gzc.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 二分查找
 * @Author: guozongchao
 * @Date: 2020/8/11 13:15
 */
public class BinarySearch implements SearchStrategy{

    @Override
    public int searchOne(int[] array, int key) {
//        return searchOne(array, 0, array.length - 1, key);   //递归版本

        //非递归版本
        int left=0;
        int right=array.length-1;

        while(left<=right){
            int mid = (left + right) / 2;
            if(array[mid]>key){
                right=mid-1;
                continue;
            } else if(array[mid]<key){
                left=mid+1;
                continue;
            }else {
                return mid;
            }
        }
        return -1;
    }

    @Override
    public List<Integer> searchMore(int[] array, int key) {
        return searchMore(array, 0, array.length - 1, key);
    }

    //递归版本的二分查找
    public int searchOne(int[] array, int left, int right, int key) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        if (array[mid] > key) {
            return searchOne(array, left, mid - 1, key);
        } else if (array[mid] < key) {
            return searchOne(array, mid + 1, right, key);
        } else {
            return mid;
        }
    }

    public List<Integer> searchMore(int[] array, int left, int right, int key) {
        List<Integer> results = new ArrayList<>();

        if (left > right) {
            return results;
        }

        int mid = (left + right) / 2;

        if (array[mid] > key) {
            return searchMore(array, left, mid - 1, key);
        } else if (array[mid] < key) {
            return searchMore(array, mid + 1, right, key);
        } else {
            int i=mid-1;
            while (array[i] == key) {
                results.add(i);
                i--;
            }
            results.add(mid);
            i=mid+1;
            while(array[i]==key){
                results.add(i);
                i++;
            }
            return results;
        }
    }
}
